package com.wlc.base.sorting.sort;

import java.util.Arrays;

/**
 * @author 王立朝
 * @date 2022/2/22
 * @description:
 */
public class demo {

    /**
     * 归并排序 更快，比插入排序（insertionSort）还要快
     *
     * @param array
     * @return
     */
    public static int[] mergeSort(int[] array) {
        if (array.length < 2) {
            return array;
        }
        int mid = array.length / 2;
        int[] left = Arrays.copyOfRange(array, 0, mid);
        int[] right = Arrays.copyOfRange(array, mid, array.length);
        return merge(mergeSort(left), mergeSort(right));
    }

    /**
     * 归并排序——将两段排序好的数组结合成一个排序数组
     *
     * @param left
     * @param right
     * @return
     */
    public static int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        for (int index = 0, i = 0, j = 0; index < result.length; index++) {
            if (i >= left.length) {

                result[index] = right[j++];
            } else if (j >= right.length) {
                result[index] = left[i++];
            } else if (left[i] > right[j]) {
                result[index] = right[j++];
            } else {
                result[index] = left[i++];
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] array = SortDemo.initArray(1200);
        long start = System.currentTimeMillis();
        int[] sort = mergeSort(array);
        long end = System.currentTimeMillis();
        long time1 = end - start;
        System.out.println("time1 = " + time1);
        long time2 = SortDemo.comapare2(array);
        System.out.println("time2 = " + time2);

    }
}
